1. Field of the Invention
This invention relates to a device for correcting errors by a long-distance code used in information storage on optical disks, magnetic disks or the like, or in data communication.
Error-correcting codes for correcting multiple words (hereinafter referred to as "a long-distance code"), such as BCH codes and Read-Solomon codes, are being used in information storage on optical disks, magnetic disks or the like, or in data communication, etc.
The present invention relates to a device for correcting errors by a long-distance code as mentioned above by decoding them. This invention is an improvement on an error-correcting device disclosed in Japanese Patent Application No. 63-218443 filed, by the applicant of the present patent application and laid open on Mar. 7, 1990 in KOKAI Application No. 2-67826. The improvement consists in diminution in device size and augmentation in speed.
2. Description of the Related Art
To correct errors in multiple words by means of a long-distance code such as BCH codes and Read-Solomon codes, it is necessary to generate syndromes from the received data so as to obtain the coefficients of an error-position polynomial. The error-position polynomial is a polynomial the root of which consists of a value that corresponds to the error position. By obtaining the respective coefficients of the error-position polynomial, the data position where the error has occurred can be calculated.
In the following explanation, a Read-Solomon code on a Galois field GF (2.sup.8) will be taken as an example. The code is capable of 4-word correction (t=4) (1 word is composed of 8 bits, and 255 words form 1 block).
Generally, an error-position polynomial .sigma.(x) can be defined by the following equation:
.sigma.(x)=X.sup.4 +.sigma..sub.3 X.sup.3 +.sigma..sub.2 X.sup.2 +.sigma..sub.1 X+.sigma..sub.0 ( 1)
There exists the following relationship between the coefficients .sigma..sub.0 to .sigma..sub.3 in the above equation (1) and syndromes S.sub.0 to S.sub.7 : ##EQU1##
By transforming this matrix by transposing the right-hand side member of the equation (2) to the left-hand side, the following equation (3) is obtained: ##EQU2##
Further, by effecting left-hand elementary transformation on the above equation (3), the following equation (4) is obtained: ##EQU3##
From this equation (4), the coefficients .sigma..sub.0 to .sigma..sub.3 can be obtained as the following equations (5): ##EQU4##
The following relationship exists between the error patterns Y.sub.1 to Y.sub.4 and the syndromes S.sub.0 to S.sub.7 ; ##EQU5## where V.sub.0 to Vhd 3 represent the error positions obtained from the equation (1) on the basis of the above-mentioned coefficients .sigma..sub.0 to .sigma..sub.3.
By effecting left-hand side elementary transformation on this equation (6) as in the case of the above equation (2), the following equation (7) can be obtained: ##EQU6##
From this equation (7), the error patterns Y.sub.1 to Y.sub.4 can be obtained as the following equation (8): ##EQU7##
As is apparent from the above equations (4) and (8), both the coefficients .sigma..sub.0 to .sigma..sub.3 of the error-position polynomial and the error patterns Y.sub.1 to Y.sub.4 can be obtained by effecting left-hand side elementary transformation on the given matrix.
Thus, in the construction of conventional long-distance code error correcting devices, the coefficients .sigma..sub.0 to .sigma..sub.3 of the error-position polynomial and the error patterns Y.sub.1 to Y.sub.4 can be obtained by effecting left-hand side elementary transformation on the given matrix.
Generally, in effecting correction with a long-distance code, the following five steps of followed:
(1) Generating syndromes;
(2) Obtaining the error-position polynomial;
(3) Obtaining the error positions;
(4) Obtaining the error patterns; and
(5) Correcting the errors.
In error-correcting devices, the steps (2) and (4) are effected by an integrally formed circuit for obtaining the error-position polynomial and the error pattern, thereby attaining dimunution in circuit size and augmentation in speed.
Thus, one problem with error-correcting devices is that the circuit for performing step (3), i.e., the circuit for locating the error position, has to be separately provided as external equipment.